package com.interview;

import java.util.ArrayList;

public class Sort
{
	
	public void quicksort(int[] a, int low, int high)
	{
		int pivot;
		if (low < high)
		{
			pivot = partition(a, low, high);
			quicksort(a, low, pivot -1);
			quicksort(a, pivot+1, high);
		}
	}
	
	public  int  partition(int[] a, int low, int high)
	{
		int pivot, p_pos;
		p_pos = low;
		pivot = a[p_pos];
		for (int i = low + 1; i <= high; i++)
		{
			if (a[i] > pivot)
			{
				p_pos++;
				swap(a, p_pos, i);
			}
		}
		swap(a, low, p_pos);
		return p_pos;
	}
	
	public void swap(int[] a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	public static void main(String[] args)
	{
		int[] vec = new int[]{37, 47, 23, -5, 19, 56};
		int temp;
		
		//Selection Sort
		long begin = System.currentTimeMillis();
		for (int i = 0; i < vec.length; i++)
		{
			for (int j = i; j < vec.length; j++)
			{
				if (vec[j] > vec[i])
				{
					temp = vec[i];
					vec[i] = vec[j];
					vec[j] = temp;
				}
			}
			
		}
		long end = System.currentTimeMillis();
		System.out.println("selection sort cost time -->"+(end-begin));
		
		for (int i : vec)
			System.out.print(i+", ");
		System.out.println("");
		
		//bubble sort
		begin = System.currentTimeMillis();
		for (int i = 0; i < vec.length; i++)
		{
			for (int j = 0; j < vec.length-1; j++)
			{
				if (vec[j+1] > vec[j])
				{
					temp = vec[j+1];
					vec[j+1] = vec[j];
					vec[j] = temp;
				}
			}
		}
		end= System.currentTimeMillis();
		System.out.println("bubble sort cost time-->"+(end-begin));
		
		for (int i : vec)
			System.out.print(i+", ");
		System.out.println("");
		
		//insertion sort
		
		int[] data = new int[]{37, 47, 23, -5, 19, 56};
		begin = System.currentTimeMillis();
		for (int i = 1; i < data.length; i++)
		{
			int j = i;
			System.out.println("arr["+(j - 1)+"]-->"+data[j - 1]+"   arr["+i+"]-->"+data[i]);
			while (j>0&& data[j - 1] > data[i])
			{
				data[j] = data[j-1]; 
				--j;
				
			}
			data[j] = data[i];
		}
		end = System.currentTimeMillis();
		System.out.println("insertion sort cost time -->"+(end-begin));
		
		for (int i : data)
			System.out.print(i+", ");
		System.out.println("");
		
		//qucik sort
		Sort s = new Sort();
		begin = System.currentTimeMillis();
		s.quicksort(vec, 0, 5);
		end = System.currentTimeMillis();
		System.out.println("quick sort cost time -->"+ (end-begin));
		for (int i : vec)
			System.out.print(i+", ");
	}
}


